package com.zdp.leetcodeMiddle;

import java.util.HashMap;
import java.util.Map;

public class LRU缓存 {
  /*
  * 设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。
  * 缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。
  * 当缓存被填满时，它应该删除最近最少使用的项目。
    它应该支持以下操作： 获取数据 get 和 写入数据 put 。
    获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
    写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，
    * 它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
  * */
    public static void main(String[] args) {
        LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);    // 该操作会使得密钥 2 作废
        System.out.println(cache.get(2));
        cache.put(4, 4);    // 该操作会使得密钥 1 作废
        cache.get(1);       // 返回 -1 (未找到)
        cache.get(3);       // 返回  3
        cache.get(4);
    }
}
/*
* 其实可以用一个队列来维持最近使用的缓存
* 在队首的元素 是最长时间没有被使用到的缓存
* 在队尾的元素 是最近被使用到的缓存
* 当缓存满时，就删除队首元素，然后从队尾插入
* 当使用到队列中缓存时，将该缓存元素移动到队尾
* 因为涉及到移动元素，所以队列可以用链表来实现；
* 为了避免每次使用时，都要遍历队列找到该元素所在的位置，然后才对其进行操作
* 可以使用 哈希表来优化查找，即键：缓存的key，值：链表的结点；这样子就可以快速定位到要操作的缓存
* 因为要对结点进行删除，插入操作，所以使用双向链表更方便。不需要辅助结点来实现插入和删除操作。
* */
class LRUCache {
    Map<Integer, ListNode11> map = new HashMap<Integer, ListNode11>();
    ListNode11 head;
    ListNode11 tail;
    int length;
    int count;
    public LRUCache(int capacity) {
        length = capacity;
        count = 0;
        //使用哨兵
        head = new ListNode11();
        tail = new ListNode11();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        ListNode11 value = map.get(key);
        if(value==null)
            return -1;
        //有值，就输出，然后将该结点放到尾结点
        value.pre.next = value.next;
        value.next.pre = value.pre;
        //插入到尾部
        tail.pre.next = value;
        value.pre = tail.pre;
        value.next = tail;
        tail.pre = value;
        return value.val;
}

    public void put(int key, int value) {
        //首先判断 缓存中是否有该值，有的话，就先更新位置，然后再更新值
        if(get(key)==-1){
            //缓存中没有该值
            //要进行插入
            if(count>=length){
                //先删除，再插入
                ListNode11 remove = head.next;
                remove.next.pre = head;
                head.next = remove.next;
                map.remove(remove.key);
                count--;
            }
            //插入
            ListNode11 node = new ListNode11();
            node.val = value;
            node.key = key;
            tail.pre.next = node;
            node.pre = tail.pre;
            node.next = tail;
            tail.pre = node;
            map.put(key,node);
            count++;
        }else{
            //缓存中有该值，更新一下值就可以了
            ListNode11 p = map.get(key);
            p.val = value;
        }
    }
}
class ListNode11{
    int key;
    int val;
    ListNode11 next;
    ListNode11 pre;
}
